package io.adrainty.algorithm.mars;

import java.util.*;

/**
 * 小M的数组变换
 * @link <a href="https://www.marscode.cn/practice/364l85wv6oo6lq?problem_id=7424418560667303980">...</a>
 * @author adrainty
 * @version v1.0.0
 * @since 2024/11/28 下午9:10
 */
public class Solution017 {

    private Solution017() {}

    public static String solution(int n, int[] a) {
        // 获取素因子集合
        Set<Integer> ans = new HashSet<>();
        for (int num : a) {
            ans.addAll(getPrimeFactors(num));
        }
        return ans.size() <= a.length? "Yes": "No";
    }

    /**
     * 获取一个数的素因子集合
     * @param num 待求解的数
     * @return 素因子集合
     */
    private static Set<Integer> getPrimeFactors(int num) {
        Set<Integer> factors = new HashSet<>();
        for (int i = 2; i * i <= num; i++) {
            while (num % i == 0) {
                factors.add(i);
                num /= i;
            }
        }
        if (num > 1) {
            factors.add(num);
        }
        return factors;
    }

}
